package com.fang.algorithm.zuo.linked;

import java.util.Objects;

/**
 * @author fanglingxiao
 * @version 1.0
 * @description 双链表结构实现双端队列
 * @date 2022/4/23 12:28 上午
 **/
public class Test05_DoubleLinkedListMockDoubleQueue {

    public static class DoubleNode<T> {
        private T value;
        private DoubleNode<T> next;
        private DoubleNode<T> last;

        public DoubleNode(T value) {
            this.value = value;
        }
    }

    public static class Queue<T> {
        private int size;
        private DoubleNode<T> head;
        private DoubleNode<T> tail;

        public Queue() {
            this.size = 0;
            head = null;
            tail = null;
        }

        public void offerHead(T data) {
            DoubleNode<T> dataNode = new DoubleNode<>(data);
            if (tail == null) {
                tail = dataNode;
                head = dataNode;
            } else {
                dataNode.next = head;
                head.last = dataNode;
                // 头节点左移
                head = dataNode;
            }
            size++;
            System.out.print(data + " ");
        }

        public T pollHead() {
            T data = null;
            if (head == null) {
                return null;
            }
            size--;
            data = head.value;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                head = head.next;
                head.last = null;
            }
            System.out.print(Objects.isNull(data) ? "" : data + " ");
            return data;
        }

        public void offerTail(T data) {
            DoubleNode<T> dataNode = new DoubleNode<>(data);
            if (tail == null) {
                tail = dataNode;
                head = dataNode;
            } else {
                tail.next = dataNode;
                dataNode.last = tail;
                tail = dataNode;
            }
            size++;
            System.out.print(data + " ");
        }

        public T pollTail() {
            T data = null;
            if (tail == null) {
                return null;
            }
            size--;
            data = tail.value;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                tail = tail.last;
                tail.next = null;
            }
            System.out.print(Objects.isNull(data) ? "" : data + " ");
            return data;
        }
    }

    public static void main(String[] args) {
        Queue<Integer> queue = new Queue<>();
        for (int i = 0; i < 10; i++) {
            queue.offerHead(i);
        }
        System.out.println();
        while (true) {
            if (null == queue.pollTail()) {
                break;
            }
        }
        System.out.println();
        for (int i = 0; i < 10; i++) {
            queue.offerTail(i);
        }
        System.out.println();
        while (true) {
            if (null == queue.pollHead()) {
                break;
            }
        }
    }

}
